Embedded Devices are increasingly being used to communicate sensitive information and are required to include security measures. Usually, embedded devices have limited resources as they are desired to be small. Therefore security mechanisms, such as encryption, authentication and verification, implemented on an embedded device need to be very efficient in terms of memory and computation requirements.
It is well known that data can be encrypted and then decrypted by utilizing a pair of keys, one of which is public and one of which is private. The keys are mathematically related such that data encrypted using the public key can be decrypted using the private key. It is also well known that a signature created with the private key can be verified utilizing the public key, and that anyone without the private key cannot generate a signature that will be validated.
The most well-known public key cryptosystems are those based on integer factorization and discrete logarithms in finite groups. It is also well known that by using computations in an elliptic curve defined over a finite field, it is possible to achieve an increased security level for the same key size or, conversely, the same security level for a shorter key.
Thus, elliptic curve encryption schemes are very suitable for the embedded environment, as the key sizes are much smaller than in the widely-used RSA schemes and require less memory. RSA is a registered trademark or trademark of RSA Security, Inc.
In an elliptic curve based public-key scheme, there are a number of system parameters that must be shared by all participants in order to make the scheme work. We shall term this information a set of system parameters. The set of system parameters typically consists of the definitional terms of the elliptic curve to be used, as well as a designated generator point G, represented by x- and y-coordinates. The elliptic curve defining parameters are typically designated a and b, where the group of points on the elliptic curve is defined by the equation Ep(a,b) for which y2=x3+ax+b, modulo p or the group E2m(a,b) for which y2+xy=x3+ax2+b, modulo 2m. The parameter p or m (which defines the finite field of definition) is also part of the set of system parameters. In another embodiment, the group is a finite field and the system parameters are the order of the field and the generator element. The system parameters can be programmed on the device during manufacturing and may be defined during design phase, as they can be shared by all users safely. In an embedded device, a memory (a first memory) holding the system parameters should be tamper resistant. An example of a temper resistant memory is unchangeable ROM.
In addition to the system parameters, an embedded device must store a public key consisting of a point on the elliptic curve, P, defined by x and y coordinates. The public key (P) is a scalar multiplication of that generator point by a private key, n. The corresponding private key may be held by a signing or decrypting party, not the embedded device. The point P, however, has to be programmed into the device later, when the public-private key pair is generated, to ensure secure key distribution process and to allow for multiple users with different keys on the same system. This programming will be done outside of the device manufacturer environment, and therefore the technology supporting this capability must be different. Memory must be provided that is one-time programmable in a post device-manufacturing environment. This type of memory is very expensive with current technology.
US patent “Elliptic Curve Encryption” U.S. Pat. No. 6,618,483B1 explores a concept of reducing transmission bandwidth by transmitting only one coordinate plus one bit of a public key in elliptic curve encryption. This scheme is used in a system where the encrypting party uses a key provided by a trusted party. The encrypting party is capable of recovering the complete public key, since the given information, one coordinate plus one bit of information about the other coordinate is sufficient for an elliptic curve point reconstruction.
Other techniques for using partial key information exist include, for example, hashing the key and storing only the hash of the key or a portion of the hash of the key. However, this technique requires additional functionality on the device, namely that of a cryptographically strong hash (for RSA use).